"""
题目：给定单链表头节点、插入位置（从0开始）和新值，在指定位置插入值为新值的节点，若位置无效（小于0或大于链表长度）则不插入，返回原链表头节点。

"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


"""在链表指定位置pos插入新节点，pos从0开始，位置无效则返回原链表"""
def insert_at_position(head, pos, new_val):
    # 步骤1：处理位置为0的情况（开头插入）
    if pos == 0:
        new_node = ListNode(new_val, next=head)
        return new_node

    # 步骤2：创建新节点，遍历找到插入位置的前一个节点
    new_node = ListNode(new_val)
    current = head
    current_pos = 0  # 当前节点的位置（从0开始）
    # 遍历到插入位置的前一个节点（current_pos = pos-1），或到链表末尾
    while current and current_pos < pos - 1:
        current = current.next
        current_pos += 1

    # 步骤3：判断位置是否有效（current非空说明pos <= 链表长度）
    if current:
        # 插入节点：新节点next指向current.next，current.next指向新节点
        new_node.next = current.next
        current.next = new_node
    return head


def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
if __name__ == "__main__":
    # 测试1：中间位置插入（pos=2）
    head1 = create_linked_list([1, 2, 4])
    new_head1 = insert_at_position(head1, 2, 3)
    print(traverse_linked_list(new_head1))  # 输出: [1, 2, 3, 4]

    # 测试2：末尾位置插入（pos=3，链表长度3）
    head2 = create_linked_list([1, 2, 3])
    new_head2 = insert_at_position(head2, 3, 4)
    print(traverse_linked_list(new_head2))  # 输出: [1, 2, 3, 4]

    # 测试3：无效位置插入（pos=5，链表长度3）
    head3 = create_linked_list([1, 2, 3])
    new_head3 = insert_at_position(head3, 5, 4)
    print(traverse_linked_list(new_head3))  # 输出: [1, 2, 3]